package ljl.codetop300;

public class _1004_longest_ones {

  static class off_bisect {
    public int longestOnes(int[] nums, int k) {
      int n = nums.length;
      int[] P = new int[n + 1];
      for (int i = 1; i <= n; ++i) {
        P[i] = P[i - 1] + (1 - nums[i - 1]);
      }

      int ans = 0;
      for (int right = 0; right < n; ++right) {
        int left = binarySearch(P, P[right + 1] - k);
        ans = Math.max(ans, right - left + 1);
      }
      return ans;
    }

    public int binarySearch(int[] P, int target) {
      int low = 0, high = P.length - 1;
      while (low < high) {
        int mid = (high - low) / 2 + low;
        if (P[mid] < target) {
          low = mid + 1;
        } else {
          high = mid;
        }
      }
      return low;
    }
  }

  static class copy_bisect {
    public int longestOnes(int[] nums, int k) {
      int[] p = new int[nums.length + 1];
      for (int i = 1; i < p.length; i++) {
        p[i] = p[i - 1] + (1 - nums[i - 1]);
      }
      int res = 0;
      for (int i = 0; i < nums.length; i++) {
        /**
         * 这个不写注释不可能懂：
         * 是 p[right] - p[left - 1] <= k
         * 所以是 p[left - 1] >= p[right] - k
         * 找第一个比右边大的 left
         */
        int left = bisect(p, p[i + 1] - k);
        res = Math.max(res, i - left + 1);
      }
      return res;
    }
    int bisect(int[] p, int k) {
      int l = 0, r = p.length - 1;
      while (l < r) {
        int mid = (l + r) / 2;
        if (p[mid] < k) l = mid + 1;
        else r = mid;
      }
      return l;
    }
  }

  /**
   * 还是这个快
   */
  static class off_sliding_window {
    public int longestOnes(int[] nums, int k) {
      int n = nums.length;
      int left = 0, lsum = 0, rsum = 0;
      int ans = 0;
      for (int right = 0; right < n; ++right) {
        rsum += 1 - nums[right];
        while (lsum < rsum - k) {
          lsum += 1 - nums[left];
          ++left;
        }
        ans = Math.max(ans, right - left + 1);
      }
      return ans;
    }
  }

  static class copy_sliding_window {
    public int longestOnes(int[] nums, int k) {
      int lsum = 0;
      int rsum = 0;
      int max = 0;
      int left = 0;
      for (int right = 0; right < nums.length; right++) {
        rsum += 1 - nums[right];
        // rsum - lsum <= k
        // -> lsum >= rsum - k 不满足就得移动
        while (lsum < rsum - k) {
          lsum += 1 - nums[left++];
        }
        max = Math.max(max, right - left + 1);
      }
      return max;
    }
  }

  /**
   * 他说他很丝滑
   */
  static class smooth {
    public int longestOnes(int[] A, int K) {
      int len = A.length;
      int r = 0, l = 0; // 对应原理1
      int zeroCounter = 0, res = 0; // zeroCounter表示修改了几次0，也可以不用counter，直接修改K值
      while (r < len) {
        if (A[r] == 0) {
          zeroCounter++;
        }
        r++; // 对应原理2，3
        while (zeroCounter > K) {
          if (A[l] == 0) {
            zeroCounter--;
          }
          l++; // 对应原理2，4
        }
        res = Math.max(res, r - l); // 对应原理5
      }
      return res;
    }
  }

  static class copy_smooth {
    public int longestOnes(int[] A, int K) {
      int zero = 0;
      int left = 0;
      int res = 0;
      for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) zero++;
        while (zero > K) {
          if (A[left++] == 0) zero--;
        }
        res = Math.max(res, i - left + 1);
      }
      return res;
    }
  }

}
